<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Title</title>
</head>
<body>
	<button onclick="addNode()">增加</button>
</body>
<script>
	//实现一个双向链表， 具备添加节点、删除节点、在特定位置插入节点、查找节点、遍历等功能
	/**
	 * 双向链表节点类
	 * @class
	 */
	class Node {
		/**
		 * 构造函数，创建一个链表节点
		 * @param {any} data - 节点存储的数据
		 */
		constructor(data) {
			this.data = data
			this.prev = null
			this.next = null
		}
	}

	/**
	 * 双向链表类
	 * @class
	 */
	class DoublyLinkedLists{
		constructor() {
			this.head = null
			this.tail = null
			this.size = 0
		}

		/**
		 * 在链表末尾添加新节点
		 * @param {any} data - 要添加的数据
		 */
		append(data){
			const newNode = new Node(data)
			// 空链表处理
			if (!this.head){
				this.head = newNode
				this.tail = newNode
			} else {
				// 非空链表追加
				newNode.prev = this.tail
				this.tail.next = newNode
				this.tail = newNode
			}
			this.size++
		}

		/**
		 * 在指定位置插入新节点
		 * @param {number} position - 插入位置索引 (0~size)
		 * @param {any} data - 要插入的数据
		 * @returns {Error|null} 越界时返回错误对象
		 */
		appendAt(position,data){
			// 位置有效性检查
			if (position < 0 || position > this.size){
				return new Error('Index out of bounds')
			}
			const newNode = new Node(data)

			// 头部插入处理
			if(position === 0){
				this.head.prev = newNode
				newNode.next = this.head
				this.head = newNode
			}
			// 尾部插入处理（复用append方法）
			else if(position === this.size){
				this.append(data)
				this.size--  // 抵消append中的size增加
			}
			// 中间位置插入
			else {
				// 定位到插入位置的前驱节点
				let current = this.head
				for(let i = 0; i < position - 1; i++){
					current = current.next
				}
				// 四步指针调整完成插入
				newNode.next = current.next
				current.next.prev = newNode
				newNode.prev = current
				current.next = newNode
			}
			this.size++
		}

		/**
		 * 删除指定位置的节点
		 * @param {number} position - 要删除的位置索引 (0~size-1)
		 * @returns {Error|null} 越界时返回错误对象
		 */
		removeAt(position){
			// 位置有效性检查
			if(position < 0 || position > this.size-1){
				return new Error('Index out of bounds')
			}

			// 单节点链表删除处理
			if (this.size === 1){
				this.head = null
				this.tail = null
			}
			// 删除头节点
			else if (position === 0){
				this.head.next.prev = null
				this.head = this.head.next
			}
			// 删除尾节点
			else if (position === this.size - 1){
				this.tail.prev.next = null
				this.tail = this.tail.prev
			}
			// 删除中间节点
			else {
				// 定位到要删除的节点
				let current = this.head
				for(let i = 0; i < position; i++){
					current = current.next
				}
				// 双指针调整跳过当前节点
				current.prev.next = current.next
				current.next.prev = current.prev
			}
			this.size--
		}

		/**
		 * 查找包含指定数据的节点
		 * @param {any} data - 要查找的数据
		 * @returns {Node|null} 找到返回节点，否则返回null
		 */
		find(data){
			let current = this.head
			// 遍历链表查找数据
			while (current){
				if (current.data === data){
					return current
				}
				current = current.next
			}
			return null
		}

		/**
		 * 正向遍历链表，返回数据数组
		 * @returns {Array} 包含所有节点数据的数组
		 */
		traverse(){
			const result = []
			let current = this.head
			// 从头节点开始遍历
			while (current){
				result.push(current.data)
				current = current.next
			}
			return result
		}

		/**
		 * 反向遍历链表，返回数据数组
		 * @returns {Array} 包含所有节点数据的数组（逆序）
		 */
		reverseTraverse(){
			const result = []
			let current = this.tail
			// 从尾节点开始遍历
			while (current){
				result.push(current.data)
				current = current.prev
			}
			return result
		}
	}

	const list = new DoublyLinkedLists();
	
	list.append(1);
	list.append(2);
	list.append(3);
	list.appendAt(1, 4); // 链表现在是 1 -> 4 -> 2 -> 3
	console.log(list.traverse())     // 输出: 1, 4, 2, 3
	
	list.removeAt(1);    // 链表现在是 1 -> 2 -> 3
	console.log(list.traverse())     // 输出: 1, 2, 3
	
	console.log(list.find(2)); // 输出: Node { data: 2, next: Node { ... }, prev: Node { ... } }
	
	console.log(list.reverseTraverse());   // 输出: 3, 2, 1
</script>
</html>